package gr.idocs.workshop.service;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class ConcurrentSorter {
	static int numCores = Runtime.getRuntime().availableProcessors();

	public static ArrayList<String> parallel_sort(ArrayList<String> arr) {
		// split the array in chunks to be processed
		final ArrayList<ArrayList<String>> chunks = new ArrayList<ArrayList<String>>();
		int chunkSize = arr.size() / numCores > 0 ? arr.size() / numCores : 1;
		numCores = numCores > chunkSize ? chunkSize : numCores;
		for (int tid = 0; tid < numCores; tid++) {
			// calc begining and end of piece 
			int begin = tid * chunkSize;
			int end = begin + chunkSize;
			if (tid == numCores - 1) {
				// if we are doing the last piece, go to the end of the array 
				end = arr.size();
			}
			ArrayList<String> chunk = new ArrayList<String>();
			// copy the elements into the chunk 
			for (int j = 0, i = begin; i < end; i++) {
				chunk.add(arr.get(i));
			}
			chunks.add(chunk);
		}

		class Sorter implements Runnable {
			private int tid;
			private Logger logger = LoggerFactory.getLogger(Sorter.class);

			public Sorter(int id) {
				tid = id;
			}

			public void run() {
				// sort our piece 
				ArrayList<String> chunk = chunks.get(tid);
				Collections.sort(chunk);
			}
		}

		ExecutorService executor = Executors.newFixedThreadPool(numCores);

		for (int id = 0; id < numCores; id++) {
			Runnable r = new Sorter(id);
			executor.execute(r);
		}

		// This will make the executor accept no new threads
		// and finish all existing threads in the queue
		executor.shutdown();
		// Wait until all threads are finish
		while (!executor.isTerminated()) {

		}

		// Merge Single Threaded 

		ArrayList<String> result = chunks.get(0);
		for (int i = 1; i < numCores; i++) {
			Set<List<String>> set = new HashSet<List<String>>();
			set.add(result);
			set.add(chunks.get(i));
			result = (ArrayList<String>) merge(set);
		}
		return result;
	}

	public static List<String> merge(Set<List<String>> lists) {
		List<String> result = new ArrayList<String>();

		int totalSize = 0; // every element in the set
		for (List<String> l : lists) {
			totalSize += l.size();
		}

		boolean first;
		List<String> lowest = lists.iterator().next(); // the list with the lowest item to add

		while (result.size() < totalSize) { // while we still have something to add
			first = true;

			for (List<String> l : lists) {
				if (!l.isEmpty()) {
					if (first) {
						lowest = l;
						first = false;
					} else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
						lowest = l;
					}
				}
			}
			result.add(lowest.get(0));
			lowest.remove(0);
		}
		return result;
	}

}
